package DataStructure.graph;

import java.util.ArrayDeque;
import java.util.Deque;

//矩阵图,dfs和bfs都是从起点开始枚举每个位置
public class Matrix {
    private static int n;//行数
    private static int m;//列数
    private static int[][] g=new int[n][m];
    private static boolean[][] mark=new boolean[n][m];//访问标志
    private static int[][] dirs={{-1,0},{0,-1},{0,1},{1,0}};//方向
    private static Deque<int[]> q=new ArrayDeque<>();//bfs中添加起点

    //访问
    public static void f(int r,int c){
        System.out.println(r+" "+c+" "+g[r][c]);
    }

    //递归dfs(起点需要先标记)
    public static void recursiveDFS(int r,int c){
        f(r,c);
        for (int[] dir : dirs) {
            int nr=r+dir[0],nc=c+dir[1];
            if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                mark[nr][nc]=true;
                recursiveDFS(nr,nc);
            }
        }
    }
    //回溯dfs,实质上是枚举起点到终点的每条路径
    public static void backTrackDFS(int r,int c,int tr,int tc){
        if(r==tr&&c==tc)
            return;
        for (int[] dir : dirs) {
            int nr=r+dir[0],nc=c+dir[1];
            if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                mark[nr][nc]=true;
                backTrackDFS(nr,nc,tr,tc);
                mark[nr][nc]=false;
            }
        }
    }
    //非递归dfs
    public static void nonRecursiveDFS(int r,int c) {
        Deque<int[]> s=new ArrayDeque<>();
        mark[r][c]=true;
        s.add(new int[]{r,c});
        while (!s.isEmpty()){
            int[] cur=s.pollLast();//从最后进入的开始遍历
            f(cur[0],cur[1]);
            for (int[] dir : dirs) {
                int nr=cur[0]+dir[0],nc=cur[1]+dir[1];
                if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                    mark[nr][nc]=true;//入队标记,防止重复添加
                    s.add(new int[]{nr,nc});
                }
            }
        }
    }

    //非递归bfs
    public static void nonRecursiveBFS(int r,int c){
        Deque<int[]> q=new ArrayDeque<>();
        mark[r][c]=true;
        q.add(new int[]{r,c});//起点入队
        while (!q.isEmpty()){
            int[] cur=q.poll();//从先进入的开始遍历
            f(cur[0],cur[1]);//该点已经标记
            //后面节点入队
            for (int[] dir : dirs) {
                int nr=cur[0]+dir[0],nc=cur[1]+dir[1];
                if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                    mark[nr][nc]=true;//入队后标记
                    q.add(new int[]{nr,nc});
                }

            }
        }
    }
    //按层非递归bfs
    public static void nonRecursiveBFSByLevel(int r,int c){
        int level=0;//当前层
        Deque<int[]> q=new ArrayDeque<>();
        mark[r][c]=true;
        q.add(new int[]{r,c});//起点入队
        while (!q.isEmpty()){
            int size=q.size();//当前层数量
            for (int i = 0; i < size; i++) {
                int[] cur=q.poll();//从先进入的开始遍历
                f(cur[0],cur[1]);
                //下一层入队
                for (int[] dir : dirs) {
                    int nr=cur[0]+dir[0],nc=cur[1]+dir[1];
                    if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                        mark[nr][nc]=true;
                        q.add(new int[]{nr,nc});
                    }
                }
            }
            level++;
        }
    }
    //递归bfs(起点需要先标记)
    public static void recursiveBFS(){
        if(q.isEmpty()) return;
        int[] cur=q.poll();
        f(cur[0],cur[1]);
        for (int[] dir : dirs) {
            int nr=cur[0]+dir[0],nc=cur[1]+dir[1];
            if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                mark[nr][nc]=true;
                q.add(new int[]{nr,nc});
            }
        }
        recursiveBFS();
    }
    //按层递归bfs(起点需要先标记)
    public static void recursiveBFSByLevel(int level){
        if(q.isEmpty()) return;
        int size=q.size();
        for (int i = 0; i < size; i++) {
            int[] cur=q.poll();
            f(cur[0],cur[1]);
            for (int[] dir : dirs) {
                int nr=cur[0]+dir[0],nc=cur[1]+dir[1];
                if(nr>=0&&nr<n&&nc>=0&&nc<m&&!mark[nr][nc]){
                    mark[nr][nc]=true;
                    q.add(new int[]{nr,nc});
                }
            }
        }
        recursiveBFSByLevel(level+1);
    }
}
